package syf.rank;


public class RadixRank {
    public static void main(String[] args) {
        int max=8000000;
        int[] arr=new int[max];
        //8万个随机的数组排序
        for (int i=0;i<max;i++){
            arr[i]=(int)(Math.random()*100000);
        }
//        int[]arr={53,3,542,748,14,214};
//        System.out.println(Arrays.toString(arr));
        long now=System.currentTimeMillis();
        radix(arr);
        long end=System.currentTimeMillis();
        System.out.println(end-now);
    }
    /**
     * 基数排序
     * @param arr 需要排序的数组，排序好后的数组也为arr因为传递进去的是地址
     */
    public static void radix(int[] arr){
        //创建桶和桶能存放的数据数量以最坏的计算，桶有10个，每个桶能装传进来的数组数量多个数据
        int[][] bucket=new int[10][arr.length];
        //累计每个桶中放了多少个数据
        int[] bucketCount=new int[bucket.length];
        //标记这个数应该放哪个组
        int index;
        //最高的数有几位就进行几轮
        int max=arr[0];
        int count;
        //找出最大的数
        for (int i=1;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        //获取最大数的位数
        int maxLength=(max+"").length();
        //要进行的轮数为最大数的位数
        for (int m=0,n=1;m<maxLength;m++,n*=10) {
            for (int value : arr) {
                //取个位
                index = value / n % 10;
                //将这个值放进对应的桶中
                bucket[index][bucketCount[index]++] = value;
            }
            //arr数组索引
            count = 0;
            //将桶中的值取出放回到arr数组中
            for (int i = 0; i < bucket.length; i++) {
                //当这个桶中数量不为0时，才进行取出
                if (bucketCount[i] != 0) {
                    for (int j = 0; j < bucketCount[i]; j++) {
                        arr[count++] = bucket[i][j];
                    }
                }
                //取完之后将桶中的个数清零
                bucketCount[i] = 0;
            }
        }
//        System.out.println(Arrays.toString(arr));

        /*
        //开始放第一轮,先看个位
        for (int i=0;i<arr.length;i++){
            //取个位
            index=arr[i] % 10;
            //将这个值放进对应的桶中
            bucket[index][bucketCount[index]++]=arr[i];
        }
        int count=0;
        //将桶中的值取出放回到arr数组中
        for (int i=0;i<bucket.length;i++){
            //当这个桶中数量不为0时，才进行取出
            if (bucketCount[i]!=0) {
                for (int j = 0; j < bucketCount[i]; j++) {
                    arr[count++] = bucket[i][j];
                }
            }
            //取完之后将桶中的个数清零
            bucketCount[i]=0;
        }
        System.out.println(Arrays.toString(arr));
        for (int i=0;i<arr.length;i++){
            //取十位
            index=arr[i] /10 % 10;
            //将这个值放进对应的桶中
            bucket[index][bucketCount[index]++]=arr[i];
        }
        count=0;
        //将桶中的值取出放回到arr数组中
        for (int i=0;i<bucket.length;i++){
            //当这个桶中数量不为0时，才进行取出
            if (bucketCount[i]!=0) {
                for (int j = 0; j < bucketCount[i]; j++) {
                    arr[count++] = bucket[i][j];
                }
            }
            //取完之后将桶中的个数清零
            bucketCount[i]=0;
        }
        System.out.println(Arrays.toString(arr));
        for (int i=0;i<arr.length;i++){
            //取百位
            index=arr[i] /100 % 10;
            //将这个值放进对应的桶中
            bucket[index][bucketCount[index]++]=arr[i];
        }
        count=0;
        //将桶中的值取出放回到arr数组中
        for (int i=0;i<bucket.length;i++){
            //当这个桶中数量不为0时，才进行取出
            if (bucketCount[i]!=0) {
                for (int j = 0; j < bucketCount[i]; j++) {
                    arr[count++] = bucket[i][j];
                }
            }
            //取完之后将桶中的个数清零
            bucketCount[i]=0;
        }
        System.out.println(Arrays.toString(arr));
        */
    }
}
